package com.atcumt.xiaoyuan;

import java.util.*;

/**
 * 给定一个单词列表 words 和一个整数 k ，返回前 k 个出现次数最多的单词。
 *
 * 返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率， 按字典顺序 排序。
 *
 * 输入: words = ["i", "love", "leetcode", "i", "love", "coding"], k = 2
 * 输出: ["i", "love"]
 * 解析: "i" 和 "love" 为出现次数最多的两个单词，均为2次。
 * 注意，按字母顺序 "i" 在 "love" 之前。
 */
public class HJOD002 {

    public static void main(String[] args) {
        String[] words = new String[]{"the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"};
        int k = 4;
        HJOD002 hjod002 = new HJOD002();
        List<String> res = hjod002.topKFrequent(words, k);
//        res.forEach(System.out::println);
        System.out.println(res);
    }

    public List<String> topKFrequent(String[] words, int k) {
        Map<String, Integer> wordFrequents = new HashMap<>();
        for (String word : words) {
            wordFrequents.put(word, wordFrequents.getOrDefault(word, 0) + 1);
        }
        PriorityQueue<String> priorityQueue = new PriorityQueue<>(new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                if (wordFrequents.get(o1) == wordFrequents.get(o2)) {
                    return o1.compareTo(o2);
                }
                // 根据出现频率倒序排列
                return wordFrequents.get(o2) - wordFrequents.get(o1);
            }
        });
        for (String s : wordFrequents.keySet()) {
            priorityQueue.add(s);
        }
        List<String> result = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            result.add(priorityQueue.poll());
        }
        return result;
    }

}
